//
// Created by 刘振舟 on 2024/6/29.
//
#include "deque.h"
#include <stdlib.h>

// 初始化双端队列
void deque_init(Deque *deque) {
    deque->front = NULL;
    deque->back = NULL;
    deque->size = 0;
}

// 销毁双端队列
void deque_destroy(Deque *deque) {
    while (deque->front != NULL) {
        DequeNode *temp = deque->front;
        deque->front = deque->front->next;
        free(temp->data); // 如果数据是动态分配的，需要释放
        free(temp);
    }
    deque->back = NULL;
    deque->size = 0;
}

// 获取双端队列中元素个数
size_t deque_size(const Deque *deque) {
    return deque->size;
}

// 判断双端队列是否为空
int deque_empty(const Deque *deque) {
    return deque->size == 0;
}

// 从头部入队
void deque_push_front(Deque *deque, void *data) {
    DequeNode *new_node = (DequeNode *)malloc(sizeof(DequeNode));
    if (new_node == NULL) {
        return; // 内存分配失败
    }
    new_node->data = data;
    new_node->next = deque->front;
    new_node->prev = NULL;

    if (deque_empty(deque)) {
        deque->back = new_node;
    } else {
        deque->front->prev = new_node;
    }
    deque->front = new_node;
    deque->size++;
}

// 从头部出队
void *deque_pop_front(Deque *deque) {
    if (deque_empty(deque)) {
        return NULL;
    }
    DequeNode *front_node = deque->front;
    void *data = front_node->data;
    deque->front = front_node->next;
    if (deque->front != NULL) {
        deque->front->prev = NULL;
    } else {
        deque->back = NULL;
    }
    free(front_node);
    deque->size--;
    return data;
}

// 从尾部入队
void deque_push_back(Deque *deque, void *data) {
    DequeNode *new_node = (DequeNode *)malloc(sizeof(DequeNode));
    if (new_node == NULL) {
        return; // 内存分配失败
    }
    new_node->data = data;
    new_node->next = NULL;
    new_node->prev = deque->back;

    if (deque_empty(deque)) {
        deque->front = new_node;
    } else {
        deque->back->next = new_node;
    }
    deque->back = new_node;
    deque->size++;
}

// 从尾部出队
void *deque_pop_back(Deque *deque) {
    if (deque_empty(deque)) {
        return NULL;
    }
    DequeNode *back_node = deque->back;
    void *data = back_node->data;
    deque->back = back_node->prev;
    if (deque->back != NULL) {
        deque->back->next = NULL;
    } else {
        deque->front = NULL;
    }
    free(back_node);
    deque->size--;
    return data;
}
